
"""
701. 二叉搜索树中的插入操作
"""
from typing import Optional

from com.siyuan.TreeNode import TreeNode


class Solution:

    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        """
        遍历二叉树
        """
        if not root:
            return TreeNode(val)
        # 前序位置
        if val < root.val:
            root.left = self.insertIntoBST(root.left, val)
        # 中序位置
        if val > root.val:
            root.right = self.insertIntoBST(root.right, val)
        # 后序位置
        return root
